package leetcode_day._2023._11;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 907.子数组的最小值之和
 * 算法: 单调栈
 *
 * @author yezh
 * @date 2023/11/27 13:24
 */
public class _27 {

    public int sumSubarrayMins(int[] arr) {
        int n = arr.length, mod = (int) (1e9 + 7);
        // leftMinIdx: 当前元素的左边第一次小于它的元素的下标
        // rightMinIdx: 当前元素的右边第一次小于等于它的元素的下标
        // 如果都在当前元素的左右两边找值小于它的元素的下标, 那么与它相等元素值的元素就不能和它一起组成子数组, 结果就会小
        // 如果找值小于等于它的元素的下标, 那么子数组会重复
        // 所以, 在当前元素的右边(或左边)找值小于等于它的元素的下标, 在左边(或右边)找值小于它的元素的下标.
        // 这样, 当前元素能包括右边(或左边)元素值与之相同的元素, 但右边(或左边)那个与之相同元素值不会包括当前元素.
        int[] leftMinIdx = new int[n], rightMinIdx = new int[n];
        Arrays.fill(leftMinIdx, -1);
        Arrays.fill(rightMinIdx, n);
        List<Integer> st = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[i] <= arr[st.get(st.size() - 1)]) {
                rightMinIdx[st.get(st.size() - 1)] = i;
                st.remove(st.size() - 1);
            }
            st.add(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && arr[i] < arr[st.get(st.size() - 1)]) {
                leftMinIdx[st.get(st.size() - 1)] = i;
                st.remove(st.size() - 1);
            }
            st.add(i);
        }
        long ans = 0;
        // 以当前元素为最小值的子数组的数量, (a = 取值数量, 包括空) 当前元素 (b = 取值数量, 包括空), 子数组的数量 a * b
        for (int i = 0; i < n; i++)
            // 每加一个数, 就要模
            ans = (ans + (long) arr[i] * (i - leftMinIdx[i]) * (rightMinIdx[i] - i)) % mod;
        return (int) ans;
    }

}
